// 7-34 猴子选大王 (20分)
// Josephus_problem 约瑟夫环问题
// 一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

// 输入格式：
// 输入在一行中给一个正整数N（≤1000）。

// 输出格式：
// 在一行中输出当选猴王的编号。

// 输入样例：
// 11

// 输出样例：
// 7

// 开始时把所有的值状态标记为1，代表这个人在循环的队列中。我们可以不断地遍历这n个值，每当遇到在队列中的人时，
// 计数器num++（这个计数器num只在遇到status[i]==1时自增），当num==m时，这个人出列，计数器清0，
// 状态标记为0（代表这个人出列了，不在循环的队列中），同时用来记录出列人数的count++。当count==n时，n个人已经全部出列，
// 可以退出for和while了。
// ————————————————
// 版权声明：本文为CSDN博主「doubleguy」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
// 原文链接：https://blog.csdn.net/doubleguy/java/article/details/84073090
#include <stdio.h>
#include <stdlib.h>
#define NUMBER 3  // 从1报数到NUMBER
int main()
{
    int n, outN = 0, cnt = 0; // outN是出列的人数  cnt是报数的数字(从1-NUMBER循环)
    scanf("%d", &n);
    int *a = 0;
    a = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
    {
        a[i] = 1;  // 状态:1为在队列中  0为不在队列中
    }
    while (outN != n - 1) // 直到队列中只剩一人
    {
        for (int i = 0; i < n; i++)
        {
            if (a[i] == 1)  // 状态为1才报数
            {
                cnt++;
            }
            if (cnt == NUMBER)  // 报数到NUMBER就退出一个人  同时cnt归零  outN人数加一
            {
                a[i] = cnt = 0;
                outN++;
            }
            if (outN == n - 1)
            {
                break;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (a[i] == 1)
        {
            printf("%d", i + 1);
            break;
        }
    }

    return 0;
}

// 变题:从第k个人开始报数
// 方法:设置flag, 第一次遍历数组时从i == k-1时开始计数, 之后的遍历还是从0-n-1
// #include <stdio.h>
// #include <stdlib.h>
// #define NUMBER 3
// int main()
// {
//     int n, outN = 0, cnt = 0, flag = 0, k;
//     scanf("%d%d", &n, &k);
//     int *a = 0;
//     a = (int *)malloc(n * sizeof(int));
//     for (int i = 0; i < n; i++)
//     {
//         a[i] = 1;
//     }
//     while (outN != n - 1)
//     {
//         for (int i = 0; i < n; i++)
//         {
//             if (i == k - 1)
//             {
//                 flag = 1;
//             }
//             if (flag == 0)
//             {
//                 continue;
//             }
//             if (a[i] == 1)
//             {
//                 cnt++;
//             }
//             if (cnt == NUMBER)
//             {
//                 a[i] = cnt = 0;
//                 outN++;
//             }
//             if (outN == n - 1)
//             {
//                 break;
//             }
//         }
//     }
//     for (int i = 0; i < n; i++)
//     {
//         if (a[i] == 1)
//         {
//             printf("%d", i + 1);
//             break;
//         }
//     }

//     return 0;
// }